package algorithm.leetcode.I1to100;

import algorithm.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 这题我称之为动画题,把进出栈的过程画一遍就可以了
 */

public class Q94 {

    public List<Integer> inorderTraversal(TreeNode root) {
        // 注意这个返回是整数而不是node,有点微妙,提示可能要改变树的结构
        // 还是不要改原来结构的好
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();

        // 针对每个栈顶的节点,依次执行:
        // 左子树有:压栈左子树,直到左子为空
        // 取出栈顶的元素,这个元素一定没有左子树
        // 添加此节点的值到list
        // 指向右子树
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }

        return result;
    }


}
